#pragma once

#include<iostream>
#include<vector>
#include <unordered_map>
#include <map>
#include<algorithm>

#include<thread>
#include<mutex>
#include <atomic>

#include<time.h>
#include<assert.h>

//mmap所需头文件
#include <sys/mman.h>
#include <sys/types.h>
#include <unistd.h>
#include <cstdlib>
#include <cerrno>

using std::cout;
using std::endl;

#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else
	//linux
	typedef unsigned long long PAGE_ID;
#endif


//高效管理小对象内存分配

// 最大管理的对象大小：256KB
static const size_t MAX_BYTES = 256 * 1024;
// 自由链表的总数量：208个
static const size_t NFREELIST = 208;
static const size_t NPAGES = 129; // 最大管理的页数量
static const size_t PAGE_SHIFT = 13; // 页大小为8KB/页大小的移位值


// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{//VirtualAlloc 是 Windows 提供的底层内存分配函数，
//用于在进程的虚拟地址空间中分配、预留或提交内存页
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
	//mmap 可以将文件映射到内存或者分配一段虚拟内存区域
	void* ptr = mmap(nullptr, kpage << 13, PROT_READ | 
		PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
#endif
	if (ptr == nullptr)
	{
		throw std::bad_alloc();
	}
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	munmap(ptr, 0);
#endif
}



static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

// 管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		// 头插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;

		++_size;
	}

	// 批量插入
	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}

	//从内存池的自由链表中,批量弹出（分配）连续的内存块
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);

		start = _freeList;//将start（起始地址）初始化为自由链表的头部
		end = start;

		for(size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}

		//更新自由链表
		//start到end的n个块已经被取走，自由链表需要跳过这些块
		_freeList = NextObj(end);

		//这n个块组成的链表到此结束
		//避免用户使用时访问到后续未分配的块，
		//确保取出的内存块是一个独立的、边界清晰的链表
		NextObj(end) = nullptr;

		_size -= n;

	}

	void* Pop()
	{
		assert(_freeList);

		//头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		--_size;

		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

// 计算对象大小的对齐映射规则 -- 太6了
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]					8byte对齐	    freelist[0,16)
	// [128+1,1024]				16byte对齐	    freelist[16,72)
	// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
	// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)

	/*size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1)*alignNum;
		}
		else
		{
			alignSize = size;
		}

		return alignSize;
	}*/
	// 1-8
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8*1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64*1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8*1024);
		}
		else
		{
			assert(false);
			return -1;
		}
	}

	/*size_t _Index(size_t bytes, size_t alignNum)
	{
	if (bytes % alignNum == 0)
	{
	return bytes / alignNum - 1;
	}
	else
	{
	return bytes / alignNum;
	}
	}*/

	//建立 “用户申请的内存大小” 到 “FreeList 索引” 的映射关系

	// “某一个对齐粒度的区间内”，计算bytes对应的局部偏移索引
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		// 每个区间有多少个链
		static int group_array[4] = {16, 56, 56, 56};
		if(bytes <= 128){
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024){
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024){
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024){
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024){
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
		else{
			assert(false);
		}

		return -1;
	}

	// 从中心缓存一次向线程缓存（thread cache）移动多少个内存块
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小内存块（如 1 字节）一次可以移动较多数量（最多 512 个）
		// 大内存块（如接近 MAX_BYTES）一次只能移动较少数量（最少 2 个）

		// 计算最大可移动数量 = 最大字节数 / 单个块大小
		int num = MAX_BYTES / size;
		// 确保最小移动2个
		if(num < 2)
			num = 2;

		// 确保最大移动512个
		if(num > 512)
			num = 512;

		return num;
	}

	//当 PageCache 中没有足够的内存页满足需求时，
	//需要向操作系统申请连续的物理页

	// 根据单个内存对象的大小，计算出一次应该向系统申请多少个物理页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		//1. 计算单次向中心缓存申请的对象数量
		size_t num = NumMoveSize(size);

		//2. 计算这些对象所需的总内存大小
		size_t npage = num*size;

		//3. 将总字节数转换为物理页数
		npage >>= PAGE_SHIFT;//等价于 npage = npage / (1 << PAGE_SHIFT)
		//右移 PAGE_SHIFT 位，等价于总字节数除以页大小，得到所需的物理页数

		//4. 确保至少申请 1 页
		if(npage == 0)
			npage = 1;

		return npage;
	}

};

// 管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0;// 大块内存起始页的页号
	size_t _n = 0;		// 页的数量

	Span* _next = nullptr;// 双向链表的结构
	Span* _prev = nullptr;

	size_t _objSize = 0;// 该大块内存的对象大小
	size_t _useCount = 0;// 切好小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;// 切好的小块内存的自由链表

	bool _isUse = false;      // 是否在被使用
};

// 带头双向循环链表 
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		// prev newspan pos
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		// 1、条件断点
		// 2、查看栈帧

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
	
private:
	Span* _head;
public:
	std::mutex _mtx;// 桶锁
};


